
\subsection{在树 / 图上 DFS}

前置知识： DFS 基础 

\subsubsection{树上 DFS}

在树上 DFS 是这样的一个过程：先访问根节点，然后分别访问根节点每个儿子的子树。

可以用来求出每个节点的深度、父亲等信息。

\subsubsection{DFS 序列}

DFS 序列是指 DFS 调用过程中访问的节点编号的序列。

我们发现，每个子树都对应 DFS 序列中的连续一段（一段区间）。

\subsubsection{括号序列}

DFS 进入某个节点的时候记录一个左括号 \texttt{(}，退出某个节点的啥时候记录一个右括号 \texttt{)}。

每个节点会出现两次。相邻两个节点的深度相差 1。

\subsubsection{二叉树上 DFS}

（图待补）

\paragraph{先序遍历}

先访问根，再访问子节点。

\paragraph{中序遍历}

先访问左子树，再访问根，再访问右子树。

\paragraph{后序遍历}

先访问子节点，再访问根。

已知中序遍历和另外一个可以求第三个。

\subsubsection{一般图上 DFS}

对于非连通图，只能访问到起点所在的连通分量。

对于连通图，DFS 序列通常不唯一。

注：树的 DFS 序列也是不唯一的。

在 DFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，称为 DFS 树。 DFS 树是原图的一个生成树。

DFS 树有很多性质，比如用来求  强连通分量 

\subsection{BFS}

前置知识： BFS 基础 

\subsubsection{树上 BFS}

从树根开始，严格按照层次来访问节点。

BFS 过程中也可以顺便求出各个节点的深度和父亲节点。

\subsubsection{BFS 序列}

类似 BFS 序列，BFS 序列是指在 BFS 过程中访问的节点编号的序列。

\subsubsection{一般图上 BFS}

同样，如果原图不连通，只能访问到起点所在的连通分量。

BFS 序列通常也不唯一。

类似的我们也可以定义 BFS 树：在 BFS 过程中，通过记录每个节点从哪个点访问而来，可以建立一个树结构，即为 BFS 树。
